/*************************************************************************
 * File Name:    1009.cc
 * Author:       zero91
 * Mail:         jianzhang9102@gmail.com
 * Created Time: Sat 28 Sep 2013 03:13:23 PM CST
 * 
 * Description:  
 ************************************************************************/

#include <iostream>
#include <fstream>
#include <sstream>
#include <algorithm>
#include <vector>
#include <queue>
#include <stack>
#include <deque>
#include <map>
#include <set>
#include <functional>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <cmath>

using namespace std;

#define MOD 95041567
#define BASE_BELL_NUM_CNT 100000

const int factor[] = {31, 37, 41, 43, 47};
const int M[] = {3065857, 2568691, 2318087, 2210269, 2022161};
const int MP[] = {18, 25, 17, 5, 10};

long long bell[BASE_BELL_NUM_CNT];
bool visited[BASE_BELL_NUM_CNT];

void
init_data()
{
    long long cnk[50][50];

    cnk[0][0] = 1;
    cnk[1][0] = cnk[1][1] = 1;
    cnk[2][0] = 1, cnk[2][1] = 2, cnk[2][2] = 1;

    for (int n = 3; n < 50; ++n) {
        cnk[n][0] = cnk[n][n] = 1;
        for (int k = 1; k < n; ++k) {
            cnk[n][k] = (cnk[n - 1][k] + cnk[n - 1][k - 1]) % MOD;
        }
    }
    memset(visited, false, sizeof(visited));
    
    bell[0] = bell[1] = 1, bell[2] = 2;
    visited[0] = visited[1] = visited[2] = true;
    for (int n = 2; n + 1 < 50; ++n) {
        bell[n + 1] = 0;
        for (int k = 0; k <= n; ++k) {
            bell[n + 1] += cnk[n][k] * bell[k] % MOD;
            bell[n + 1] %= MOD;
        }
        visited[n + 1] = true;
    }
}

long long
touchard(long long n, int p)
{
    if (n < BASE_BELL_NUM_CNT && visited[n]) return bell[n] % p;

    int i;
    long long t = 1;

    for (i = 1; i < BASE_BELL_NUM_CNT; ++i) {
        t *= p;
        if (n < t) {
            t /= p;
            break;
        }
    }
    return ((i - 1) * touchard(n - t + 1, p) + touchard(n - t, p)) % MOD;
}

int
main(int argc, char *argv[])
{
    int T;
    long long n, res[5], ans;

    init_data();

    for (int n = 50; n < BASE_BELL_NUM_CNT; ++n) {
        for (int i = 0; i < 5; ++i) {
            res[i] = touchard(n, factor[i]);
        }
        ans = 0;
        for (int i = 0; i < 5; ++i) {
            ans += (MP[i] * M[i] % MOD) * res[i] % MOD;
        }
        bell[n] = ans;
        visited[n] = true;
    }

    cin >> T;
    while (T--) {
        cin >> n;
        for (int i = 0; i < 5; ++i) {
            res[i] = touchard(n, factor[i]);
        }
        ans = 0;
        for (int i = 0; i < 5; ++i) {
            ans += (MP[i] * M[i] % MOD) * res[i] % MOD;
        }
        cout << ans % MOD << endl;
    }
    return 0;
}
